#include <string.h>
#include <debug.h>

/* Copies SIZE bytes from SRC to DST, which must not overlap.
   Returns DST. */
void *memcpy(void *dst_, const void *src_, size_t size)
{
    unsigned char *dst = dst_;
    const unsigned char *src = src_;

    ASSERT(dst != NULL || size == 0);
    ASSERT(src != NULL || size == 0);

    while (size-- > 0)
        *dst++ = *src++;

    return dst_;
}

/* Copies SIZE bytes from SRC to DST, which are allowed to
   overlap.  Returns DST. */
void *memmove(void *dst_, const void *src_, size_t size)
{
    unsigned char *dst = dst_;
    const unsigned char *src = src_;

    ASSERT(dst != NULL || size == 0);
    ASSERT(src != NULL || size == 0);

    if (dst < src)
    {
        while (size-- > 0)
            *dst++ = *src++;
    }
    else
    {
        dst += size;
        src += size;
        while (size-- > 0)
            *--dst = *--src;
    }

    return dst;
}

/* Find the first differing byte in the two blocks of SIZE bytes
   at A and B.  Returns a positive value if the byte in A is
   greater, a negative value if the byte in B is greater, or zero
   if blocks A and B are equal. */
int memcmp(const void *a_, const void *b_, size_t size)
{
    const unsigned char *a = a_;
    const unsigned char *b = b_;

    ASSERT(a != NULL || size == 0);
    ASSERT(b != NULL || size == 0);

    for (; size-- > 0; a++, b++)
        if (*a != *b)
            return *a > *b ? +1 : -1;
    return 0;
}

/* Finds the first differing characters in strings A and B.
   Returns a positive value if the character in A (as an unsigned    char) is greater, a negative value if the character in B (as
   an unsigned char) is greater, or zero if strings A and B are
   equal. */
int strcmp(const char *a_, const char *b_)
{
    const unsigned char *a = (const unsigned char *)a_;
    const unsigned char *b = (const unsigned char *)b_;

    ASSERT(a != NULL);
    ASSERT(b != NULL);

    while (*a != '\0' && *a == *b)
    {
        a++;
        b++;
    }

    return *a < *b ? -1 : *a > *b;
}

/* Returns a pointer to the first occurrence of CH in the first
   SIZE bytes starting at BLOCK.  Returns a null pointer if CH
   does not occur in BLOCK. */
void *memchr(const void *block_, int ch_, size_t size)
{
    const unsigned char *block = block_;
    unsigned char ch = ch_;

    ASSERT(block != NULL || size == 0);

    for (; size-- > 0; block++)
        if (*block == ch)
            return (void *)block;

    return NULL;
}

/* Finds and returns the first occurrence of C in STRING, or a
   null pointer if C does not appear in STRING.  If C == '\0'
   then returns a pointer to the null terminator at the end of
   STRING. */
char *strchr(const char *string, int c_)
{
    char c = c_;

    ASSERT(string != NULL);

    for (;;)
        if (*string == c)
            return (char *)string;
        else if (*string == '\0')
            return NULL;
        else
            string++;
}

/* Returns the length of the initial substring of STRING that
   consists of characters that are not in STOP. */
size_t strcspn(const char *string, const char *stop)
{
    size_t length;

    for (length = 0; string[length] != '\0'; length++)
        if (strchr(stop, string[length]) != NULL)
            break;
    return length;
}

/* Returns a pointer to the first character in STRING that is
   also in STOP.  If no character in STRING is in STOP, returns a
   null pointer. */
char *strpbrk(const char *string, const char *stop)
{
    for (; *string != '\0'; string++)
        if (strchr(stop, *string) != NULL)
            return (char *)string;
    return NULL;
}

/* Returns a pointer to the last occurrence of C in STRING.
   Returns a null pointer if C does not occur in STRING. */
char *strrchr(const char *string, int c_)
{
    char c = c_;
    const char *p = NULL;

    for (; *string != '\0'; string++)
        if (*string == c)
            p = string;
    return (char *)p;
}

/* Returns the length of the initial substring of STRING that
   consists of characters in SKIP. */
size_t strspn(const char *string, const char *skip)
{
    size_t length;

    for (length = 0; string[length] != '\0'; length++)
        if (strchr(skip, string[length]) == NULL)
            break;
    return length;
}

/* Returns a pointer to the first occurrence of NEEDLE within
   HAYSTACK.  Returns a null pointer if NEEDLE does not exist
   within HAYSTACK. */
char *strstr(const char *haystack, const char *needle)
{
    size_t haystack_len = strlen(haystack);
    size_t needle_len = strlen(needle);

    if (haystack_len >= needle_len)
    {
        size_t i;

        for (i = 0; i <= haystack_len - needle_len; i++)
            if (!memcmp(haystack + i, needle, needle_len))
                return (char *)haystack + i;
    }

    return NULL;
}

/* Breaks a string into tokens separated by DELIMITERS.  The
   first time this function is called, S should be the string to
   tokenize, and in subsequent calls it must be a null pointer.
   SAVE_PTR is the address of a `char *' variable used to keep
   track of the tokenizer's position.  The return value each time
   is the next token in the string, or a null pointer if no
   tokens remain.

   This function treats multiple adjacent delimiters as a single
   delimiter.  The returned tokens will never be length 0.
   DELIMITERS may change from one call to the next within a
   single string.

   strtok_r() modifies the string S, changing delimiters to null
   bytes.  Thus, S must be a modifiable string.  String literals,
   in particular, are *not* modifiable in C, even though for
   backward compatibility they are not `const'.

   Example usage:

   char s[] = "  String to  tokenize. ";
   char *token, *save_ptr;

   for (token = strtok_r (s, " ", &save_ptr); token != NULL;
        token = strtok_r (NULL, " ", &save_ptr))
     printf ("'%s'\n", token);

   outputs:

     'String'
     'to'
     'tokenize.'
*/
char *strtok_r(char *s, const char *delimiters, char **save_ptr)
{
    char *token;

    ASSERT(delimiters != NULL);
    ASSERT(save_ptr != NULL);

    /* If S is nonnull, start from it.
       If S is null, start from saved position. */
    if (s == NULL)
        s = *save_ptr;
    ASSERT(s != NULL);

    /* Skip any DELIMITERS at our current position. */
    while (strchr(delimiters, *s) != NULL)
    {
        /* strchr() will always return nonnull if we're searching
           for a null byte, because every string contains a null
           byte (at the end). */
        if (*s == '\0')
        {
            *save_ptr = s;
            return NULL;
        }

        s++;
    }

    /* Skip any non-DELIMITERS up to the end of the string. */
    token = s;
    while (strchr(delimiters, *s) == NULL)
        s++;
    if (*s != '\0')
    {
        *s = '\0';
        *save_ptr = s + 1;
    }
    else
        *save_ptr = s;
    return token;
}

/* Sets the SIZE bytes in DST to VALUE. */
void *memset(void *dst_, int value, size_t size)
{
    unsigned char *dst = dst_;

    ASSERT(dst != NULL || size == 0);

    while (size-- > 0)
        *dst++ = value;

    return dst_;
}

/* Returns the length of STRING. */
size_t strlen(const char *string)
{
    const char *p;

    ASSERT(string != NULL);

    for (p = string; *p != '\0'; p++)
        continue;
    return p - string;
}

/* If STRING is less than MAXLEN characters in length, returns
   its actual length.  Otherwise, returns MAXLEN. */
size_t strnlen(const char *string, size_t maxlen)
{
    size_t length;

    for (length = 0; string[length] != '\0' && length < maxlen; length++)
        continue;
    return length;
}

/* Copies string SRC to DST.  If SRC is longer than SIZE - 1
   characters, only SIZE - 1 characters are copied.  A null
   terminator is always written to DST, unless SIZE is 0.
   Returns the length of SRC, not including the null terminator.

   strlcpy() is not in the standard C library, but it is an
   increasingly popular extension.  See
   http://www.courtesan.com/todd/papers/strlcpy.html for
   information on strlcpy(). */
size_t strlcpy(char *dst, const char *src, size_t size)
{
    size_t src_len;

    ASSERT(dst != NULL);
    ASSERT(src != NULL);

    src_len = strlen(src);
    if (size > 0)
    {
        size_t dst_len = size - 1;
        if (src_len < dst_len)
            dst_len = src_len;
        memcpy(dst, src, dst_len);
        dst[dst_len] = '\0';
    }
    return src_len;
}

/* Concatenates string SRC to DST.  The concatenated string is
   limited to SIZE - 1 characters.  A null terminator is always
   written to DST, unless SIZE is 0.  Returns the length that the
   concatenated string would have assuming that there was
   sufficient space, not including a null terminator.

   strlcat() is not in the standard C library, but it is an
   increasingly popular extension.  See
   http://www.courtesan.com/todd/papers/strlcpy.html for
   information on strlcpy(). */
size_t strlcat(char *dst, const char *src, size_t size)
{
    size_t src_len, dst_len;

    ASSERT(dst != NULL);
    ASSERT(src != NULL);

    src_len = strlen(src);
    dst_len = strlen(dst);
    if (size > 0 && dst_len < size)
    {
        size_t copy_cnt = size - dst_len - 1;
        if (src_len < copy_cnt)
            copy_cnt = src_len;
        memcpy(dst + dst_len, src, copy_cnt);
        dst[dst_len + copy_cnt] = '\0';
    }
    return src_len + dst_len;
}
